package priority;

/**
 * description:
 * author:张腾
 * date:2021-04-08
 */

/**
 * 最大优先队列 获取并删除的是队列中的最大值
 * 优先队列，底层使用堆实现  ≈堆
 * @param <T>
 */
public class MaxPriorityQueue<T extends Comparable<T>> {
    //记录堆中的元素
    private T[] items;
    //记录堆中元素的个数
    private int N;

    public MaxPriorityQueue(int capacity){
        this.items = (T[]) new Comparable[capacity+1];
        this.N = 0;
    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N==0;
    }

    private boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }

    private void exch(int i,int j){
        T tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    public void insert(T t){
        items[++N] = t;
        swim(N);
    }

    //删除优先队列中的最大元素，并返回这个元素
    public T delMax(){
        T max = items[1];
        exch(1,N);
        items[N] = null;
        N--;
        sink(1);
        return max;
    }

    private void swim(int k){
        while (k>1){
            if (less(k/2,k)){
                exch(k/2,k);
            }

            k = k/2;
        }
    }

    private void sink(int k){
        while (2*k<=N){
            int max;
            if (2*k+1<=N){
                if (less(2*k+1,2*k)){
                    max = 2*k;
                }else {
                    max = 2*k+1;
                }
            }else{
                max = 2*k;
            }
            if (!less(k,max)){
                break;
            }

            exch(k,max);
            k = max;
        }
    }

}
